package org.liaohailong.helloworld.stack;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Author: liaohailong
 * Time: 2021/5/18 10:02
 * Describe:
 */
public class Solution1 {

    public void reverseString(char[] s) {
        if (s.length == 1) return;
        reverseString(s, s.length - 1, 0);
    }

    private void reverseString(char[] s, int from, int to) {
        if (from > to) {
            char temp = s[to];
            s[to] = s[from];
            s[from] = temp;
            from--;
            to++;
            reverseString(s, from, to);
        }
    }


    // LC 两两交换链表中的节点
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode temp = head.next;
        head.next = null;
        ListNode next = temp.next;
        temp.next = head;
        head.next = swapPairs(next);
        return temp;
    }

    // LC 杨辉三角形
    // f(i,j) = f(i-1,j-1) + f(i-1,j)
    // i or j equals 1 return 1
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 1; i <= numRows; i++) {
            ArrayList<Integer> row = new ArrayList<>();
            for (int j = 1; j <= i; j++) {
                if (j == 1 || j == i)
                    row.add(1);
                else if (i > 1) {
                    int upIndex = i - 2;
                    List<Integer> upRows = result.get(upIndex);
                    int left = j - 2;
                    int top = j - 1;
                    int leftVal = upRows.get(left);
                    int topVal = upRows.get(top);
                    int val = leftVal + topVal;
                    row.add(val);
                }
            }
            result.add(row);
        }
        return result;
    }

    // 杨辉三角形2
    public List<Integer> getRow(int rowIndex) {
        int numRows = rowIndex + 1;
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 1; i <= numRows; i++) {
            ArrayList<Integer> row = new ArrayList<>();
            for (int j = 1; j <= i; j++) {
                if (j == 1 || j == i)
                    row.add(1);
                else if (i > 1) {
                    int upIndex = i - 2;
                    List<Integer> upRows = result.get(upIndex);
                    int left = j - 2;
                    int top = j - 1;
                    int leftVal = upRows.get(left);
                    int topVal = upRows.get(top);
                    int val = leftVal + topVal;
                    row.add(val);
                }
            }
            result.add(row);
        }
        return result.get(rowIndex);
    }

    /**
     * 杨辉三角形函数求值
     *
     * @param i 行数
     * @param j 列数
     * @return 值
     */
    private int f(int i, int j) {
        if (j == 1 || j == i) return 1;
        return f(i - 1, j - 1) + f(i - 1, j);
    }

    // LC 递归反转链表 - 递归方式
//    public ListNode reverseList(ListNode head) {
//        if (head == null || head.next == null) return head;
//
//        ListNode next = head.next;
//        ListNode node = next.next;
//        head.next = null;
//        next.next = head;
//        return _reverseList(next, node);
//    }
//
//    private ListNode _reverseList(ListNode head, ListNode node) {
//        if (node == null) {
//            return head;
//        } else {
//            ListNode next = node.next;
//            node.next = head;
//            return _reverseList(node, next);
//        }
//    }


    // LC 反转链表 - 非递归
//    public ListNode reverseList(ListNode head) {
//        if (head == null || head.next == null) return head;
//
//        ListNode newHead = head.next;
//        head.next = null;
//        ListNode node = newHead.next;
//        newHead.next = head;
//        while (node != null) {
//            ListNode next = node.next;
//            node.next = newHead;
//            newHead = node;
//            node = next;
//        }
//        return newHead;
//    }

    // LC 反转链表 - 非递归 教科书版
//    public ListNode reverseList(ListNode head) {
//        ListNode prev = null;
//        ListNode curr = head;
//        while (curr != null) {
//            ListNode next = curr.next;
//            curr.next = prev;
//            prev = curr;
//            curr = next;
//        }
//        return prev;
//    }

    // LC 反转链表 - 递归
    public ListNode reverseList(ListNode head) {
        return _reverseList(null, head);
    }

    private ListNode _reverseList(ListNode prev, ListNode curr) {
        if (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
            return _reverseList(prev, curr);
        } else return prev;
    }

    private static final int maxCap = 1 << 30;

    public int tableFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return n < 0 ? 1 : (n >= maxCap ? maxCap : n + 1);
    }

    Map<Integer, Integer> cache = new HashMap<>();

    // LC fibonacci
    public int fib(int n) {
        if (cache.containsKey(n)) {
            return cache.get(n);
        }
        int result;
        if (n < 2) {
            result = n;
        } else {
            result = fib(n - 1) + fib(n - 2);
        }
        cache.put(n, result);
        return result;
    }

    // LC 爬楼梯
//    public int climbStairs(int n) {
//        int[] res = new int[]{0};
//        climbStairs(1, 0, n, res);
//        climbStairs(2, 0, n, res);
//        return res[0];
//    }
//
//    private void climbStairs(int step, int curr, int target, int[] res) {
//        int total = curr + step;
//        if (total == target) {
//            res[0]++;
//            return;
//        }
//        if (total > target) {
//            return;
//        }
//
//        climbStairs(1, total, target, res);
//        climbStairs(2, total, target, res);
//    }

    // LC 爬楼梯
//    public int climbStairs(int n) {
//        int[] memo = new int[n + 1];
//        return climbStairs(0, n, memo);
//    }
//
//    private int climbStairs(int i, int n, int[] memo) {
//        System.out.println("i = " + i + ", n = " + n + ", memo = " + Arrays.toString(memo));
//        if (i > n) return 0;
//        if (i == n) return 1;
//        if (memo[i] > 0) return memo[i];
//        memo[i] = climbStairs(i + 1, n, memo) + climbStairs(i + 2, n, memo);
//        return memo[i];
//    }

    // LC 爬楼梯
//    public int climbStairs(int n) {
//        int[][] q = {{1, 1}, {1, 0}};
//        int[][] res = pow(q, n);
//        return res[0][0];
//    }
//
//    public int[][] pow(int[][] a, int n) {
//        int[][] ret = {{1, 0}, {0, 1}};
//        while (n > 0) {
//            if ((n & 1) == 1) {
//                ret = multiply(ret, a);
//            }
//            n >>= 1;
//            a = multiply(a, a);
//        }
//        return ret;
//    }
//
//    public int[][] multiply(int[][] a, int[][] b) {
//        int[][] c = new int[2][2];
//        for (int i = 0; i < 2; i++) {
//            for (int j = 0; j < 2; j++) {
//                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
//            }
//        }
//        return c;
//    }

    // LC 爬楼梯
    public int climbStairs(int n) {
        double sqrt5 = Math.sqrt(5);
        double fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
        return (int) (fibn / sqrt5);
    }

    // LC 二叉树的最大深度
    public int maxDepth(TreeNode root) {
        int[] res = new int[]{0};
        _maxDepth(root, 1, res);
        return res[0];
    }

    public void _maxDepth(TreeNode node, int depth, int[] res) {
        if (node == null) return;
        if (res[0] < depth) res[0] = depth;
        depth++;
        TreeNode left = node.left;
        TreeNode right = node.right;
        _maxDepth(left, depth, res);
        _maxDepth(right, depth, res);
    }

//    public double myPow(double x, double N) {
//        double n = N;
//        if (x == 1 || x == 0) return x;
//        if (n >= 0) {
//            if (n == 1) return x;
//            if (n == 0) return 1;
//            if (n % 2 == 1) return x * myPow(x * x, (n - 1) / 2);
//            else return myPow(x * x, n / 2);
//        } else {
//            return myPow(1 / x, -n);
//        }
//    }

    // LC Pow(x,n)
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }

        return fastPow(x, N);
    }

    private double fastPow(double x, long n) {
        if (n == 0) {
            return 1.0;
        }
        double half = fastPow(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }


    public static final class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static final class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
